package BinaryTreePackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class isBalanced_ {

  // 确定参数和返回值
  // 确定终止条件
  // 确定每层处理逻辑
  public boolean isBalanced(TreeNode root) {
    return getHeight(root) == -1 ? false : true;
  }
  public int getHeight(TreeNode root){
    // if root == null return -1
    if (root == null){
      return 0;
    }
    // definite the Height of root.left
    int leftHeight = getHeight(root.left);
    // when we find the subTree of Treenode is not balanced tree, we just return
    // one of subTree is not balanced means the whole tree is not balanced
    if (leftHeight == -1){return -1;}

    // definite the Height of root.right
    int rightHeight = getHeight(root.right);
    if (rightHeight == -1){return -1;}
    if (Math.abs(leftHeight-rightHeight) > 1){
      return -1;
    }
    return Math.max(leftHeight,rightHeight) + 1;
  }
}
